package QuestionDaily;

public class minDeletion_2216 {
    /**
     * 细则详见leecode
     * @param nums 下标从 0 开始的整数数组
     * @return 返回使 nums 变为美丽数组所需删除的 最少 元素数目。
     */
    public int minDeletion(int[] nums) {
        /**
         * 想法是顺序处理，从左向右拼接
         * 因为数组中奇数项一定不能等于后一个元素
         * 当遇到一个冲突时，需要选择一个进行逻辑删除
         * 3ms  58%
         */
        int count=0;
        int pre=-1;
        boolean flag=true;    //经过前面的处理后，当前数字是否是奇数位
        for(int i=0;i<nums.length; i++){
            if (flag) { //当前是奇数位
                 if (i != nums.length - 1&&nums[i] == nums[i + 1]){ //与后一个元素相同
                    if(i==nums.length-2)
                        count++;  //如果后两位数字相同，都要删除
                    count++;  //至少删除一个数字
                    pre=nums[i];
                    flag=false;  //下一个还是偶数位，还是要进行判断
                }else       //与后一位不相同，后一位无需处理
                    flag=true;
                i++;  //是否相同都需要跳过一位数字
            }else{ //需要处理的偶数位
                if(pre==nums[i]){//如果仍然与前一位相同，还是需要删除一位
                    count++;
                    pre=nums[i];
                    flag=false;
                }else
                    flag=true;
            }
        }
        //最后剩余一定是偶数个，如果不是，说明结尾有一个需要删除的数字
        if((nums.length-count)%2!=0)
            count++;
        //如果最后删除的只剩一个数字，直接全部删除
        return nums.length==count+1?nums.length:count;
    }

    /**
     * 高解3ms
     * 思路类似，但是这个很简洁
     * @param nums
     * @return
     */
    public int minDeletion2(int[] nums) {
        int n = nums.length, cnt = 0;
        for (int i = 0; i < n; i++) {
            if ((i - cnt) % 2 == 0 && i + 1 < n && nums[i] == nums[i + 1]) //若当前下标为偶数，且与下一位置元素相同，那么当前元素需被删除，令 cnt 自增。
                cnt++;
        }
        return (n - cnt) % 2 != 0 ? cnt + 1 : cnt;
    }

}
